package com.dyz.leetcode._19_greedy;

import java.util.*;

public class _45_jump {
    //超时
    private int minSteps = Integer.MAX_VALUE;
    public int jump(int[] nums) {
        if(nums.length==0){return 0;}
        List<Integer> path = new ArrayList<>();
        dfs(nums, 0, path);
        return minSteps==Integer.MAX_VALUE?0:minSteps;
    }

    private void dfs(int[] nums, int jumpedIndex, List<Integer> path){
        if(jumpedIndex==nums.length-1){
            minSteps = Math.min(minSteps, path.size());
            return;
        }

        for (int i = 1; i <=nums[jumpedIndex] ; i++) {
            if(jumpedIndex+i>=nums.length){continue;}
            path.add(i);
            dfs(nums, jumpedIndex+i, path);
            path.remove(path.size()-1);
        }
    }
    //BFS
    public int jump1(int[] nums) {
        if(nums.length==0){return 0;}
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        int level = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i=0; i<size; i++){
                int jumpedIndex = queue.poll();
                if(jumpedIndex==nums.length-1){return level;}
                for(int j=1; j<=nums[jumpedIndex];j++){
                    queue.offer(jumpedIndex+j);
                }
            }
            level++;
        }
        return 0;
    }

    //贪心算法
    public int jump2(int[] nums){
        int step = 0;
        int start=0, end = 0;
        while (end<nums.length-1){
            int maxpos = 0;
            for(int i=start; i<=end; i++){
                maxpos = Math.max(maxpos, i+nums[i]);
            }
            start = end+1;
            end = maxpos;
            step++;
        }
        return step;
    }
}
